home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 25 / CU Amiga Magazine's Super CD-ROM 25 (1998)(EMAP Images)(GB)(Track 1 of 2)[!][issue 1998-08].iso / CUCD / Programming / QuakeTools / src / libqbuild / merge.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-06-11  |  6.2 KB  |  272 lines
  1. #define    LIBQBUILD_CORE
  2. #include "../include/libqbuild.h"
  3.  
  4. bool mergedebug;            // ?
  5.  
  6. /*
  7.  * ================
  8.  * CheckColinear
  9.  * 
  10.  * ================
  11.  */
  12. void CheckColinear(register struct visfacet * f)
  13. {
  14.   int i, j;
  15.   vec3_t v1, v2;
  16.  
  17.   for (i = 0; i < f->numpoints; i++) {
  18. // skip the point if the vector from the previous point is the same
  19.     // as the vector to the next point
  20.     j = (i - 1 < 0) ? f->numpoints - 1 : i - 1;
  21.     VectorSubtract(f->pts[i], f->pts[j], v1);
  22.     VectorNormalize(v1);
  23.  
  24.     j = (i + 1 == f->numpoints) ? 0 : i + 1;
  25.     VectorSubtract(f->pts[j], f->pts[i], v2);
  26.     VectorNormalize(v2);
  27.  
  28.     if (VectorCompare(v1, v2))
  29.       Error("Colinear edge");
  30.   }
  31.  
  32. }
  33.  
  34. /*
  35.  * =============
  36.  * TryMerge
  37.  * 
  38.  * If two polygons share a common edge and the edges that meet at the
  39.  * common points are both inside the other polygons, merge them
  40.  * 
  41.  * Returns NULL if the faces couldn't be merged, or the new face.
  42.  * The originals will NOT be freed.
  43.  * =============
  44.  */
  45. struct visfacet *TryMerge(__memBase, register struct visfacet * f1, register struct visfacet * f2)
  46. {
  47.   vec_t *p1, *p2, *p3, *p4, *back;
  48.   struct visfacet *newf;
  49.   int i, j, k, l;
  50.   vec3_t normal, delta, planenormal;
  51.   vec_t dot;
  52.   struct plane *plane;
  53.   bool keep1, keep2;
  54.  
  55.   if (f1->numpoints == -1 || f2->numpoints == -1)
  56.     return NULL;
  57.   if (f1->planeside != f2->planeside)
  58.     return NULL;
  59.   if (f1->texturenum != f2->texturenum)
  60.     return NULL;
  61.   if (f1->contents[0] != f2->contents[0])
  62.     return NULL;
  63.   if (f1->contents[1] != f2->contents[1])
  64.     return NULL;
  65.  
  66. //
  67.   // find a common edge
  68.   //      
  69.   p1 = p2 = NULL;                                   // stop compiler warning
  70.  
  71.   j = 0;                                       // 
  72.  
  73.   for (i = 0; i < f1->numpoints; i++) {
  74.     p1 = f1->pts[i];
  75.     p2 = f1->pts[(i + 1) % f1->numpoints];
  76.     for (j = 0; j < f2->numpoints; j++) {
  77.       p3 = f2->pts[j];
  78.       p4 = f2->pts[(j + 1) % f2->numpoints];
  79.       for (k = 0; k < 3; k++) {
  80.     if (fabs(p1[k] - p4[k]) > EQUAL_EPSILON)
  81.       break;
  82.     if (fabs(p2[k] - p3[k]) > EQUAL_EPSILON)
  83.       break;
  84.       }
  85.       if (k == 3)
  86.     break;
  87.     }
  88.     if (j < f2->numpoints)
  89.       break;
  90.   }
  91.  
  92.   if (i == f1->numpoints)
  93.     return NULL;                                   // no matching edges
  94.  
  95. //
  96.   // check slope of connected lines
  97.   // if the slopes are colinear, the point can be removed
  98.   //
  99. #ifdef EXHAUSIVE_CHECK
  100.   if(f1->planenum >= bspMem->numbrushplanes || f1->planenum < 0)
  101.     Error("looking for nonexisting plane %d\n", f1->planenum);
  102. #endif
  103.   plane = &bspMem->brushplanes[f1->planenum];
  104.   VectorCopy(plane->normal, planenormal);
  105.   if (f1->planeside)
  106.     VectorNegate(planenormal);
  107.  
  108.   back = f1->pts[(i + f1->numpoints - 1) % f1->numpoints];
  109.   VectorSubtract(p1, back, delta);
  110.   CrossProduct(planenormal, delta, normal);
  111.   VectorNormalize(normal);
  112.  
  113.   back = f2->pts[(j + 2) % f2->numpoints];
  114.   VectorSubtract(back, p1, delta);
  115.   dot = DotProduct(delta, normal);
  116.   if (dot > CONTINUOUS_EPSILON)
  117.     return NULL;                                   // not a convex polygon
  118.  
  119.   keep1 = dot < -CONTINUOUS_EPSILON;
  120.  
  121.   back = f1->pts[(i + 2) % f1->numpoints];
  122.   VectorSubtract(back, p2, delta);
  123.   CrossProduct(planenormal, delta, normal);
  124.   VectorNormalize(normal);
  125.  
  126.   back = f2->pts[(j + f2->numpoints - 1) % f2->numpoints];
  127.   VectorSubtract(back, p2, delta);
  128.   dot = DotProduct(delta, normal);
  129.   if (dot > CONTINUOUS_EPSILON)
  130.     return NULL;                                   // not a convex polygon
  131.  
  132.   keep2 = dot < -CONTINUOUS_EPSILON;
  133.  
  134. //
  135.   // build the new polygon
  136.   //
  137.   if (f1->numpoints + f2->numpoints > MAXEDGES) {
  138. //              Error ("TryMerge: too many edges!");
  139.     return NULL;
  140.   }
  141.  
  142.   newf = NewFaceFromFace(f1, MAXEDGES);
  143.  
  144. // copy first polygon
  145.   for (k = (i + 1) % f1->numpoints; k != i; k = (k + 1) % f1->numpoints) {
  146.     if (k == (i + 1) % f1->numpoints && !keep2)
  147.       continue;
  148.  
  149.     VectorCopy(f1->pts[k], newf->pts[newf->numpoints]);
  150.     newf->numpoints++;
  151.   }
  152.  
  153. // copy second polygon
  154.   for (l = (j + 1) % f2->numpoints; l != j; l = (l + 1) % f2->numpoints) {
  155.     if (l == (j + 1) % f2->numpoints && !keep1)
  156.       continue;
  157.     VectorCopy(f2->pts[l], newf->pts[newf->numpoints]);
  158.     newf->numpoints++;
  159.   }
  160.  
  161.   RecalcFace(newf);
  162.   // mprintf("TryMerge: merged %d + %d to %d\n", f1->numpoints, f2->numpoints, newf->numpoints);
  163.  
  164.   return newf;
  165. }
  166.  
  167. /*
  168.  * ===============
  169.  * MergeFaceToList
  170.  * ===============
  171.  */
  172. struct visfacet *MergeFaceToList(__memBase, struct visfacet * face, struct visfacet * list)
  173. {
  174.   struct visfacet *newf, *f;
  175.  
  176.   for (f = list; f; f = f->next) {
  177. //CheckColinear (f);            
  178.     if (mergedebug) {
  179.       Draw_ClearWindow();
  180.       Draw_DrawFace(face);
  181.       Draw_DrawFace(f);
  182.       Draw_SetBlack();
  183.     }
  184.     newf = TryMerge(bspMem, face, f);
  185.     if (!newf)
  186.       continue;
  187.     FreeFace(face);
  188.     f->numpoints = -1;                                   // merged out
  189.  
  190.     return MergeFaceToList(bspMem, newf, list);
  191.   }
  192.  
  193. // didn't merge, so add at start
  194.   face->next = list;
  195.   return face;
  196. }
  197.  
  198. /*
  199.  * ===============
  200.  * FreeMergeListScraps
  201.  * ===============
  202.  */
  203. struct visfacet *FreeMergeListScraps(struct visfacet * merged)
  204. {
  205.   struct visfacet *head, *next;
  206.  
  207.   head = NULL;
  208.   for (; merged; merged = next) {
  209.     next = merged->next;
  210.     if (merged->numpoints == -1)
  211.       FreeFace(merged);
  212.     else {
  213.       merged->next = head;
  214.       head = merged;
  215.     }
  216.   }
  217.  
  218.   return head;
  219. }
  220.  
  221. /*
  222.  * ===============
  223.  * MergePlaneFaces
  224.  * ===============
  225.  */
  226. void MergePlaneFaces(__memBase, struct surface * plane)
  227. {
  228.   struct visfacet *f1, *next;
  229.   struct visfacet *merged;
  230.  
  231.   merged = NULL;
  232.  
  233.   for (f1 = plane->faces; f1; f1 = next) {
  234.     next = f1->next;
  235.     merged = MergeFaceToList(bspMem, f1, merged);
  236.   }
  237.  
  238. // chain all of the non-empty faces to the plane
  239.   plane->faces = FreeMergeListScraps(merged);
  240. }
  241.  
  242. /*
  243.  * ============
  244.  * MergeAll
  245.  * ============
  246.  */
  247. void MergeAll(__memBase, struct surface * surfhead)
  248. {
  249.   struct surface *surf;
  250.   int mergefaces, numsurf = 0, i;
  251.   struct visfacet *f;
  252.  
  253.   mprintf("----- MergeAll ----------\n");
  254.  
  255.   /* PROGRESS-ONLY! */
  256.   for (surf = surfhead; surf; surf = surf->next)
  257.     numsurf++;
  258.   
  259.   mergefaces = 0;
  260.   for (surf = surfhead, i = 0; surf; surf = surf->next, i++) {
  261.     MergePlaneFaces(bspMem, surf);
  262.     Draw_ClearWindow();
  263.     for (f = surf->faces; f; f = f->next) {
  264.       Draw_DrawFace(f);
  265.       mergefaces++;
  266.     }
  267.     mprogress(numsurf, i + 1);
  268.   }
  269.  
  270.   mprintf("%5i mergefaces\n", mergefaces);
  271. }
  272.